You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.
A number x is considered missing if x is in the range [lower, upper] and x is not in nums.
Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.
Each range [a,b] in the list should be output as:
"a->b"ifa != b"a"ifa == b
Example 1:
Input: nums = [0,1,3,50,75], lower = 0, upper = 99 Output: ["2","4->49","51->74","76->99"] Explanation: The ranges are: [2,2] --> "2" [4,49] --> "4->49" [51,74] --> "51->74" [76,99] --> "76->99"
Example 2:
Input: nums = [], lower = 1, upper = 1 Output: ["1"] Explanation: The only missing range is [1,1], which becomes "1".
Example 3:
Input: nums = [], lower = -3, upper = -1 Output: ["-3->-1"] Explanation: The only missing range is [-3,-1], which becomes "-3->-1".
Example 4:
Input: nums = [-1], lower = -1, upper = -1 Output: [] Explanation: There are no missing ranges since there are no missing numbers.
Example 5:
Input: nums = [-1], lower = -2, upper = -1 Output: ["-2"]
Constraints:
-109 <= lower <= upper <= 1090 <= nums.length <= 100lower <= nums[i] <= upper- All the values of
numsare unique.
Average Rating: 4.81 (36 votes)
Video Solution
Solution Article
Approach 1: Linear Scan
Intuition and Algorithm
Since the input array, nums, is sorted ascendingly and all the elements in it are within the given [lower, upper] bounds, we can simply check consecutive elements to see if they differ by one or not. If they don't, then we have found a missing range.
- When
nums[i] - nums[i-1] == 1, we know that there are no missing elements betweennums[i-1]andnums[i]. - When
nums[i] - nums[i-1] > 1, we know that the range of elements,[nums[i-1] + 1, nums[i] - 1], is missing.
However, there are two edge cases:
- Edge case 1: If we don't start with
loweras the first element of the array, we will need to include[lower, num[0] - 1]as a missing range as well.
- Edge case 2: Similarly, if we don't end with
upperas the last element of the array, we will need to include[nums[n-1] + 1, upper]as a missing range as well. Notenhere is the length of the input array,nums.
Complexity Analysis
Let N be the length of the input array.
-
Time complexity : O(N).
This is because we are only iterating over the array once, and at each step, we're performing O(1) operations. We treat the string building as O(1) because the strings can never be more than a fixed size.
-
Space complexity : O(1).
The output list has a worst case size of O(N). This case occurs when we have a missing range between each of the consecutive elements in the input array (for example, if the input array contains all even numbers between
lowerandupper). We aren't using any other additional space, beyond fixed-sized constants that don't grow with the size of the input.However, output space that is simply used to return the output (and not to do any processing) is not counted for the purpose of space complexity analysis. For this reason, the overall space complexity is O(1).
December 8, 2020 10:16 PM
Am I the only one to think that the explanation is brilliant? (visuals helps a lot) The code is also very readable, if I was an interviewer I would like to see code like this where its broken down into helper functions and the edge cases clearly called out.
December 10, 2020 4:50 PM
I did not find this easy :(
January 13, 2021 6:02 AM
Python, no extra memory, just traversing nums:
class Solution:
def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
result = []
def add(low, high):
if low > high:
return
if low == high:
result.append(str(low))
else:
result.append(str(low) + '->' + str(high))
if not nums: # edge case
add(lower, upper)
return result
add(lower, nums[0] - 1)
for x in range(len(nums)):
add(nums[x - 1] + 1, nums[x] - 1)
add(nums[-1] + 1, upper)
return result
March 9, 2021 5:31 AM
This one was asked to me.
December 14, 2020 11:17 PM
That video walkthrough was very well done. Thank you.
Last Edit: December 9, 2020 8:30 AM
Although the problem is boring, I have to admit that the provided solution is really elegant.
Thanks for the implementation so that I find my coding ability is not even close at all. :(
April 18, 2021 5:23 AM
I definetly would not categorize this as an easy problem :(
December 10, 2020 10:08 PM
Python solution with list concatenation, easier to understand.
class Solution(object):
def findMissingRanges(self, nums, lower, upper):
res = []
nums = [lower-1] + nums + [upper+1]
for i in range(1, len(nums)):
curr, prev = nums[i], nums[i-1]
if curr - prev > 1:
self.addRange(res, prev, curr)
return res
def addRange(self, res, low, high):
if low + 2 == high:
res.append(str(low+1))
else:
res.append(str(low+1) + '->' + str(high-1))
April 8, 2021 12:12 PM
My simple solution using zip()
class Solution:
def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
ans = []
for n1, n2 in zip([lower-1, *nums], [*nums, upper+1]):
if n2 - n1 == 2:
ans.append(str(n1 + 1))
elif n2 - n1 > 2:
ans.append(str(n1+1) + "->" + str(n2 - 1))
return ans
Last Edit: November 4, 2020 5:26 AM
My solution in C++
vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
vector<string> res;
int l = lower, r = upper, n = nums.size();
for (int i = 0; i <= n; i ++) {
if (i) l = nums[i - 1] + 1;
r = i == n ? upper: nums[i] - 1;
if (r == l - 1) continue;
if (r == l) {
res.push_back(to_string(l));
} else {
res.push_back(to_string(l) + "->" + to_string(r));
}
}
return res;
}
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 05/25/2021 09:05 | Accepted | 0 ms | 7 MB | cpp |
xxxxxxxxxxclass Solution {public: string get_range(int start, int end) { return start==end? to_string(start) : to_string(start)+"->"+to_string(end); } vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) { vector<string> result; int pre = lower-1; for(int i =0; i <= nums.size(); i++) { int cur = (i==nums.size()? upper+1:nums[i]); if(cur-pre>=2) result.push_back(get_range(pre+1,cur-1)); pre = cur; } return result; }};